package com.hanxiaozhang.no10leetcode.dynamicprogramming;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个正整数n，能形成多少种不同结构的二叉搜索树。
 * 约束: 1 <= n <= 19
 * 二叉搜索树概念：
 * 它或者是一棵空树，或者是具有下列性质的二叉树：
 * -若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * -若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * -它的左、右子树也分别为二叉排序树。
 * <p>
 * 实例:
 * 输入: 3
 * 输出: 5
 * 解释: Given n = 3, there are a total of 5 unique BST's:
 * <p>
 * 1     1          2         3     3
 * . \   \        /  \      /      /
 * .. 3   2     1     3    2     1
 * ./      \             /         \
 * 2        3          1             2
 *
 * @author hanxinghua
 * @create 2024/3/4
 * @since 1.0.0
 */
public class No96UniqueBinarySearchTrees {

    public static void main(String[] args) {


        System.out.println(method1(4));
    }


    /**
     * 动态规划
     * 分析思路：
     * 1. 确认root结点（即让每个数做root结点）。例如 n=3时，root=1时，分析有几种情况。root=2时，分析有几种情况。root=3时，分析有种情况。
     * 2. 确定root结点之后，因为二叉树只有左右两个子树，所以能生成几种树就是用左子树的不同结构数乘以右子树不同结构数。
     * - n=3时举例（有一个null子树，也就是说空也算一种）：
     * -- 1.root=1时，左子树为空那就是1，右子树有两个值，两个值可以变换出两种，所以右子树不同结构数就是2，所以当前情况下总个数为1*2=2
     * -- 2.root=2时，左子树一个值为1，右子树一个值也为1，同理总数为1*1=1
     * -- 3.root=3时，左子树有两个值，右子树为空，那么总数为2*1=2
     * - 按照以上思路，n=4时： 5+2+2+5=14
     * -- 1.root = 1, 左子树为空（有1种情况），右子树为3个值（有5种情况）  1*5=5
     * -- 2.root = 2，左子树为1个值（有1种情况），右子树为2个值（有2种情况）   1*2=2
     * -- 3.root = 3，左子树为2个值（有2种情况） ，右子树为1个值（有1种情况） 2*1=2
     * -- 4.root = 4，左子树为3个值（有5种情况），右子树为空（有1种情况）   5*1=5
     * <p>
     * 动态规划：
     * 设动态规划数组为dp[]，dp[0]我们代表空树的情况，空树我们也按一个空节点处理，所以先初始化dp[0] = 1，
     * 当然了dp[1]肯定也是1。
     *
     * @param n
     * @return
     */
    private static int method1(int n) {
        if (n < 0) {
            return -1;
        }
        // 1.设置记忆数组
        int[] dp = new int[n + 1];
        // 2.设置初始化值
        dp[0] = 1;
        dp[1] = 1;

        // 4.选择最优子结构 (遍历记忆表，找出最优解）
        // 遍历n
        for (int i = 2; i <= n; i++) {
            // 遍历设置root结点的情况
            for (int j = 1; j <= i; j++) {
                // 3.构建状态转移方程
                // 左子树 -> j-1 右子树 -> i - j   i相当于n  j相当于root结点
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        //  5. 回溯求解
        return dp[n];
    }

}
